package consistenthhash

import (
	"fmt"
	"hash/crc32"
	"sort"
	"strconv"
)

type Hash func([]byte) uint32
type Cycle []uint32

func (c Cycle) Len() int {
	return len(c)
}

func (c Cycle) Less(i, j int) bool {
	return c[i] < c[j]
}

func (c Cycle) Swap(i, j int) {
	c[i], c[j] = c[j], c[i]
}

type HashCycle struct {
	hash           Hash  //hash 函数
	replicas       int   // 虚拟节点和实际节点的比例
	cycle          Cycle //环
	virtualNodeMap map[uint32]string
	existsNode     map[string]struct{}
}

// NewCycle 问题 ,虚拟节点是随机生成指定的节点数,然后关联节点和实际位置的关系,如何保存生成的节点不在已经生成的节点内
func NewCycle(hash Hash, replicas int) *HashCycle {
	r := &HashCycle{
		hash:           hash,
		replicas:       replicas,
		cycle:          make([]uint32, 0, 32),
		virtualNodeMap: make(map[uint32]string),
		existsNode:     make(map[string]struct{}),
	}
	if r.hash == nil {
		r.hash = crc32.ChecksumIEEE
	}
	return r
}

//Add 如何保存节点已经生成过了,无需重复生成
func (m *HashCycle) Add(node string) {
	if node == "" {
		return
	}
	if _, ok := m.existsNode[node]; ok {
		return
	}
	for i := 0; i < m.replicas; i++ {
		vk := m.hash([]byte(node + strconv.Itoa(i*3)))
		m.cycle = append(m.cycle, vk)
		m.virtualNodeMap[vk] = node
	}
	m.existsNode[node] = struct{}{}
	sort.Sort(m.cycle)
}

//Get 计算key的hash值,获取起顺时针的下一个值
//key 表示需要查找的key 返回值为其对应的node节点,是否存在,有一个求余数的操作
func (m *HashCycle) Get(key string) (string, bool) {
	if key == "" {
		return "", false
	}
	if len(m.cycle) == 0 {
		return "", false
	}
	hashValue := m.hash([]byte(key))
	//查找虚拟节点的位置
	virtualNodeIdx := sort.Search(len(m.cycle), func(i int) bool {
		return hashValue <= m.cycle[i]
	})
	if virtualNodeIdx == len(m.cycle) {
		virtualNodeIdx = 0
	}
	//查询出虚拟节点
	virtualNode := m.cycle[virtualNodeIdx]
	return m.virtualNodeMap[uint32(virtualNode)], true
}

//CycleNodeCounts 已经存在的虚拟节点数目
func (m *HashCycle) CycleNodeCounts() int {
	return len(m.cycle)
}

func (m *HashCycle) PrintNode() {
	fmt.Printf("cycle\n%v\n", m.virtualNodeMap)
}
